Stochastic universal sampling (SUS) is a technique used in genetic algorithms for selecting potentially useful solutions for recombination. It was introduced by James Baker.[1]
SUS is a development of fitness proportionate selection which exhibits no bias and minimal spread. Where fitness proportionate selection chooses several solutions from the population by repeated random sampling, SUS uses a single random value to sample all of the solutions by choosing them at evenly spaced intervals. Described as an algorithm, pseudocode for SUS looks like:
RWS(population, f) Ptr := 0 for p in population if Ptr < f and Ptr + fitness of p > f return p Ptr := Ptr + fitness of p
SUS(population, N) F := total fitness of population Start := random number between 0 and F/N Ptrs := [Start + i*F/N | i in [0..N-1]] return [RWS(i) | i in Ptrs]
Here "RWS" describes the bulk of fitness proportionate selection (also known as "roulette wheel selection") - in true fitness proportional selection the parameter f is always a random number from 0 to F. The algorithm above is very inefficient both for fitness proportionate and stochastic universal sampling, and is intended to be illustrative rather than canonical.